{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Balanced Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isBalanced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #平衡二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树，判断它是否是高度平衡的二叉树。</p>\n",
    "\n",
    "<p>本题中，一棵高度平衡二叉树定义为：</p>\n",
    "\n",
    "<blockquote>\n",
    "<p>一个二叉树<em>每个节点 </em>的左右两个子树的高度差的绝对值不超过 1 。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg\" style=\"width: 342px; height: 221px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg\" style=\"width: 452px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,2,3,3,null,null,4,4]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在范围 <code>[0, 5000]</code> 内</li>\n",
    "\t<li><code>-10<sup>4</sup> <= Node.val <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [balanced-binary-tree](https://leetcode.cn/problems/balanced-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [balanced-binary-tree](https://leetcode.cn/problems/balanced-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[1,2,2,3,3,null,null,4,4]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.isBalanced2(root) is not None\n",
    "        \n",
    "        \n",
    "    def isBalanced2(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        height_left = self.isBalanced2(root.left)\n",
    "        height_right = self.isBalanced2(root.right)\n",
    "        if height_left is None or height_right is None:\n",
    "            return None\n",
    "        \n",
    "        if abs(height_left - height_right) <= 1:\n",
    "            return max(height_left, height_right) + 1\n",
    "        else:\n",
    "            return None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        check_list = [root]\n",
    "\n",
    "        while check_list:\n",
    "            new_list = list()\n",
    "            for c in check_list:\n",
    "                left_height = self.get_tree_height(c.left)\n",
    "                if c.left:\n",
    "                    new_list.append(c.left)\n",
    "\n",
    "                right_height = self.get_tree_height(c.right)\n",
    "                if c.right:\n",
    "                    new_list.append(c.right)\n",
    "\n",
    "                if abs(left_height - right_height) >= 2:\n",
    "                    return False\n",
    "\n",
    "            check_list = new_list\n",
    "\n",
    "        return True\n",
    "\n",
    "    def get_tree_height(self, tree):\n",
    "        \"\"\"\n",
    "        :type: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not tree:\n",
    "            return 0\n",
    "\n",
    "        level = 0\n",
    "        node_list = [tree]\n",
    "\n",
    "        while node_list:\n",
    "            temp_list = list()\n",
    "            level += 1\n",
    "            for node in node_list:\n",
    "                if node.left:\n",
    "                    temp_list.append(node.left)\n",
    "                if node.right:\n",
    "                    temp_list.append(node.right)\n",
    "            node_list = temp_list\n",
    "\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return True\n",
    "        def f(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            t = [[root]]\n",
    "            n = 1\n",
    "            while True:\n",
    "                tt = []\n",
    "                for i in t[-1]:\n",
    "                    if i.left:\n",
    "                        tt.append(i.left)\n",
    "                    if i.right:\n",
    "                        tt.append(i.right)\n",
    "                if tt:\n",
    "                    n += 1\n",
    "                    t.append(tt)\n",
    "                else:\n",
    "                    return n\n",
    "        if abs(f(root.left) - f(root.right)) <= 1:\n",
    "            return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        stack = [(False, root)]\n",
    "        depth = {None: 0}\n",
    "        while stack:\n",
    "            seen, node = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            if not seen:\n",
    "                stack.extend([(True, node), (False, node.right), (False, node.left)])\n",
    "            else:\n",
    "                if abs(depth[node.left] - depth[node.right]) > 1:\n",
    "                    return False\n",
    "                depth[node] = max(depth[node.left], depth[node.right]) + 1\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def height(self,root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        stack2 = []\n",
    "        count = 0\n",
    "        while len(stack) > 0:\n",
    "            root = stack.pop()\n",
    "            if root.left != None:\n",
    "                stack2.append(root.left)\n",
    "            if root.right != None:\n",
    "                stack2.append(root.right)\n",
    "            if len(stack) == 0:\n",
    "                stack = stack2\n",
    "                stack2 = []\n",
    "                count += 1\n",
    "        return count\n",
    "    \n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return True\n",
    "        \n",
    "        if root.left != None:\n",
    "            print('left',root.left.val,self.height(root.left))\n",
    "        else:\n",
    "            print('left',root.left,self.height(root.left))\n",
    "        if root.right != None:\n",
    "            print('right',root.right.val,self.height(root.right))\n",
    "        else:\n",
    "            print('right',root.right,self.height(root.right))\n",
    "            \n",
    "            \n",
    "            \n",
    "        if abs(self.height(root.left) - self.height(root.right)) > 1:\n",
    "            return False\n",
    "        else:\n",
    "            if self.isBalanced(root.left) and self.isBalanced(root.right):\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def is_balanced_tree(tree:TreeNode) -> bool:\n",
    "  if not tree:\n",
    "    return True\n",
    "  level_nodes = [tree]\n",
    "  node_count = 0\n",
    "  max_degree = 0\n",
    "  level_nodes_list =[]\n",
    "\n",
    "  while level_nodes:\n",
    "    level_nodes_list.append(level_nodes)\n",
    "    next_level_nodes =[]\n",
    "    for node in level_nodes:\n",
    "      node_count += 1\n",
    "      left = node.left\n",
    "      right = node.right\n",
    "      node.degree = 0\n",
    "      if left:\n",
    "        left.parent = node\n",
    "        next_level_nodes.append(left)\n",
    "      if right:\n",
    "        right.parent = node\n",
    "        next_level_nodes.append(right)\n",
    "    if next_level_nodes:\n",
    "      max_degree += 1\n",
    "    level_nodes = next_level_nodes\n",
    "  for node in level_nodes_list[-1]:\n",
    "    node.degree = 0\n",
    "  for level_nodes in reversed(level_nodes_list):\n",
    "    for node in level_nodes:\n",
    "      if hasattr(node,'parent'):\n",
    "        parent = node.parent\n",
    "        parent.degree = max(node.degree +1,parent.degree)\n",
    "  for level_nodes in level_nodes_list:\n",
    "    for node in level_nodes:\n",
    "      left_degree = node.left.degree if node.left else -1\n",
    "      right_degree = node.right.degree if node.right else -1\n",
    "      if abs(left_degree - right_degree) > 1:\n",
    "        return False\n",
    "  return True\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        return is_balanced_tree(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return depth(root)!=-1\n",
    "    \n",
    "        \n",
    "def depth(node):\n",
    "    \n",
    "    if node is None:\n",
    "        return 0\n",
    "    \n",
    "    l = depth(node.left)\n",
    "    if l==-1:\n",
    "        return -1\n",
    "    \n",
    "    r = depth(node.right)\n",
    "    if r==-1:\n",
    "        return -1\n",
    "    \n",
    "    if abs(l-r)>1:\n",
    "        return -1\n",
    "    \n",
    "    return max(l,r)+1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "def h(root):\n",
    "    if root  == None:\n",
    "        return 0\n",
    "    else:\n",
    "        return max(h(root.left),h(root.right))+1\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return True\n",
    "        elif abs(h(root.left)-h(root.right))>1:\n",
    "            return False\n",
    "        else:\n",
    "            return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def balancedHeight(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.balancedHeight(root.left)\n",
    "        right = self.balancedHeight(root.right)\n",
    "        if left < 0 or right < 0 or left-right>1 or right-left>1:\n",
    "            return -1\n",
    "        return max(left, right)+1\n",
    "        \n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.balancedHeight(root) >= 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        self.hdic ={}\n",
    "        if not root:\n",
    "            return True\n",
    "        elif abs(self.height(root.left)-self.height(root.right))>1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        \n",
    "    def height(self,root):\n",
    "        if not root:return 0;\n",
    "        if root not in self.hdic:\n",
    "            self.hdic[root]=max(self.height(root.left),self.height(root.right))+1\n",
    "        return self.hdic[root]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #recursive\n",
    "        def check(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left = check(root.left)\n",
    "            right = check(root.right)\n",
    "            if left == -1 or right == -1 or abs(left - right) > 1:\n",
    "                return -1\n",
    "            return 1 + max(left, right)\n",
    "        return check(root) != -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return self.getHeight(root) != -1\n",
    "    \n",
    "    def getHeight(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.getHeight(root.left)\n",
    "        right = self.getHeight(root.right)\n",
    "        \n",
    "        if left == -1 or right == -1:\n",
    "            return -1\n",
    "        if abs(left-right) > 1:return -1\n",
    "        return max(left, right) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: 'TreeNode') -> 'bool':\n",
    "        \n",
    "        def balance_depth(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            d_left = balance_depth(root.left)\n",
    "            d_right = balance_depth(root.right)\n",
    "            if d_left >= 0 and d_right >= 0 and abs(d_left - d_right) <= 1:\n",
    "                return max(d_left, d_right) + 1\n",
    "            else:\n",
    "                return -1\n",
    "            \n",
    "        return balance_depth(root) >= 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def depth(root,d,res):\n",
    "            if not root:\n",
    "                return res + [d-1]\n",
    "            r1 = depth(root.left,d+1,[])\n",
    "            r2 = depth(root.right,d+1,[])\n",
    "            if not r1 or not r2:\n",
    "                return False\n",
    "            if abs(max(r1) - max(r2)) > 1:\n",
    "                return False\n",
    "            else:\n",
    "                return r1+r2\n",
    "        if not depth(root,0,[]):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if root.left == None and root.right == None:\n",
    "                return 1,True\n",
    "            if root.left == None:\n",
    "                return 2,(root.right.left == None and root.right.right == None)\n",
    "            if root.right == None:\n",
    "                return 2, (root.left.left == None and root.left.right == None)\n",
    "            l = height(root.left)\n",
    "            r = height(root.right)\n",
    "            if abs(l[0]-r[0]) >1 or l[1] == False or r[1] == False:\n",
    "                return 0,False\n",
    "            return 1 + max(l[0],r[0]),True\n",
    "        if root == None or (root.left == None and root.right == None):\n",
    "            return True\n",
    "        if root.left == None:\n",
    "            return (root.right.left == None and root.right.right == None)\n",
    "        if root.right == None:\n",
    "            return (root.left.left == None and root.left.right == None)\n",
    "        l = height(root.left)\n",
    "        r = height(root.right)\n",
    "        if abs(l[0]-r[0]) > 1 or l[1] == False or r[1] == False:\n",
    "            return False\n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack=[root]\n",
    "        depth=[1]\n",
    "        maxd=0\n",
    "        while stack:\n",
    "            node=stack.pop(0)\n",
    "            d=depth.pop(0)\n",
    "            if maxd<d:\n",
    "                maxd=d\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                depth.append(d+1)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                depth.append(d+1)\n",
    "        return maxd\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            node=stack.pop(0)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                ld=self.maxDepth(node.left)\n",
    "            else:\n",
    "                ld=0\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                rd=self.maxDepth(node.right)\n",
    "            else:\n",
    "                rd=0\n",
    "            if rd>ld+1 or rd<ld-1:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:      \n",
    "        stack = []\n",
    "        node = root\n",
    "        leftDepth, rightDepth = {}, {}\n",
    "        while stack or node:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left if node.left else node.right\n",
    "            node = stack.pop() # 回溯时处理数据\n",
    "            if node:\n",
    "                leftDepth[node] = 1 + max(leftDepth[node.left], rightDepth[node.left]) if node.left else 0\n",
    "                rightDepth[node] = 1 + max(leftDepth[node.right], rightDepth[node.right]) if node.right else 0\n",
    "                if abs(leftDepth[node] - rightDepth[node]) > 1:\n",
    "                    return False\n",
    "            if stack and stack[-1].left == node:\n",
    "                node = stack[-1].right\n",
    "            else:\n",
    "                node = None # 强制退栈\n",
    "        return True\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if(not root):return True\n",
    "        return abs(self.deepth(root.left)-self.deepth(root.right))<2 and self.isBalanced(root.left) and self.isBalanced(root.right) \n",
    "\n",
    "    def deepth(self,root):  \n",
    "        res = 0\n",
    "        if(not root):return res\n",
    "        queue = [root]\n",
    "        while(queue):\n",
    "            l = len(queue)\n",
    "            for i in range(l):\n",
    "                r = queue.pop(0)\n",
    "                if(r.left):\n",
    "                    queue.append(r.left)\n",
    "                if(r.right):\n",
    "                    queue.append(r.right)\n",
    "\n",
    "            res += 1\n",
    "        return res\n",
    "\n",
    "        # # 递归 求深度 ##########################################################\n",
    "        # if(not root):return 0\n",
    "        # return 1 + max(self.deepth(root.left),self.deepth(root.right))\n",
    "        # ########################################################################\n",
    "\n",
    "    # # 官方解答 ###################################################################\n",
    "    # def height(self, root: TreeNode) -> int:\n",
    "    #     # An empty tree has height -1\n",
    "    #     if not root:\n",
    "    #         return -1\n",
    "    #     return 1 + max(self.height(root.left), self.height(root.right))\n",
    "    \n",
    "    # def isBalanced(self, root: TreeNode) -> bool:\n",
    "    #     # An empty tree satisfies the definition of a balanced tree\n",
    "    #     if not root:\n",
    "    #         return True\n",
    "\n",
    "    #     # Check if subtrees have height within 1. If they do, check if the\n",
    "    #     # subtrees are balanced\n",
    "    #     return abs(self.height(root.left) - self.height(root.right)) < 2 \\\n",
    "    #         and self.isBalanced(root.left) \\\n",
    "    #         and self.isBalanced(root.right)\n",
    "    # #################################################################################\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        left_l = self.depth(root.left)\n",
    "        right_l = self.depth(root.right)\n",
    "\n",
    "        if abs(left_l-right_l)>1:\n",
    "            return False\n",
    "\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "    \n",
    "    def depth(self,root):\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        q = [root]\n",
    "        while len(q) > 0:\n",
    "            q_l = len(q)\n",
    "            while q_l > 0:\n",
    "                r = q.pop(0)\n",
    "                if r.left:\n",
    "                    q.append(r.left)\n",
    "                if r.right:\n",
    "                    q.append(r.right)\n",
    "                q_l -= 1\n",
    "            ans += 1\n",
    "    \n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        q = [root]\n",
    "        l = 0\n",
    "        height = dict()\n",
    "        while l < len(q):\n",
    "            r = len(q)\n",
    "            for node in q[l: r]:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            l = r\n",
    "        for i in range(len(q) - 1, -1, -1):\n",
    "            node = q[i]\n",
    "            l = r = 0\n",
    "            if not node.left and not node.right:\n",
    "                height[id(node)] = 1\n",
    "            else:\n",
    "                if node.left:\n",
    "                    l = height[id(node.left)]\n",
    "                if node.right:\n",
    "                    r = height[id(node.right)]\n",
    "                if abs(l-r) > 1:\n",
    "                    return False\n",
    "                else:\n",
    "                    height[id(node)] = 1 + max(l, r)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        def maxDepth(root):\n",
    "            queue = []\n",
    "            queue.append(root)\n",
    "          \n",
    "            cen = 0\n",
    "            tmp = []\n",
    "            res = []\n",
    "            if not root:\n",
    "                return 0\n",
    "            while queue:\n",
    "                tmp = []\n",
    "              \n",
    "                for _ in range(len(queue)):\n",
    "                    a = queue.pop(0)\n",
    "                    tmp.append(a)\n",
    "                    if a.left:\n",
    "                        queue.append(a.left)\n",
    "                    if a.right:\n",
    "                        queue.append(a.right)\n",
    "\n",
    "                res.append(tmp)\n",
    "                cen += 1\n",
    "            return cen\n",
    "        def dfs(root):\n",
    "            \n",
    "            if root: \n",
    "                h1=maxDepth(root.left)\n",
    "                h2=maxDepth(root.right)\n",
    "                \n",
    "                if abs(h1-h2)>1:\n",
    "                    return False\n",
    "                if h1==1 and h2==1:\n",
    "                    return True\n",
    "                if h1==1 and h2==0:\n",
    "                    return True\n",
    "                if h1==0 and h2==1:\n",
    "                    return True \n",
    "                if h1==0 and h2==0:\n",
    "                    return True\n",
    "                else: \n",
    "                    print(h1,h2,abs(h1-h2))\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                   \n",
    "            \n",
    "         \n",
    "            \n",
    "             \n",
    "                \n",
    "               \n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        idx = [-1] * 5000\n",
    "        height = [[-1, -1] for _ in range(5000)]\n",
    "        node = [None] * 5000\n",
    "        idx[0], node[0] = 0, root\n",
    "        height[0][0] = 1\n",
    "        d = 1\n",
    "        while d > 0:\n",
    "            idx[d] += 1\n",
    "            if idx[d] > 1:  # 该层结束，回溯\n",
    "                if abs(height[d][0] - height[d][1]) > 1:\n",
    "                    return False\n",
    "                height[d - 1][idx[d - 1]] += max(height[d])\n",
    "                idx[d] = -1\n",
    "                d -= 1\n",
    "                continue\n",
    "            node[d] = node[d - 1].left if idx[d] == 0 else node[d - 1].right\n",
    "            if node[d] is None:\n",
    "                height[d][idx[d]] = 0\n",
    "            else:\n",
    "                height[d][idx[d]] = 1\n",
    "                d += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Info:\n",
    "    def __init__(self, idx=-1, height=None, node=None):\n",
    "        if height is None:\n",
    "            height = [0, 0]\n",
    "        self.idx = idx\n",
    "        self.height = height\n",
    "        self.node = node\n",
    "\n",
    "    def get_child(self, idx):\n",
    "        return self.node.left if idx == 0 else self.node.right\n",
    "\n",
    "    def check_balance(self):\n",
    "        return abs(self.height[0] - self.height[1]) <= 1\n",
    "\n",
    "    def set_current_height(self, child_heigt):\n",
    "        self.height[self.idx] = 1 + child_heigt;\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        info = [Info(0, [1, 0], root), Info()]\n",
    "        while len(info) > 1:\n",
    "            info[-1].idx += 1\n",
    "            if info[-1].idx > 1:  # 该层结束，回溯\n",
    "                now = info.pop()\n",
    "                if not now.check_balance():\n",
    "                    return False\n",
    "                info[-1].set_current_height(max(now.height))\n",
    "                continue\n",
    "            node = info[-2].get_child(info[-1].idx)\n",
    "            if node is not None:\n",
    "                info[-1].node = node\n",
    "                info.append(Info())\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def depth(a:TreeNode):\n",
    "            if not a: return 0\n",
    "            queue=[a]\n",
    "            i=0\n",
    "            while queue:\n",
    "                i += 1 \n",
    "                next_queue=[]\n",
    "                for node in queue:\n",
    "                    if node.left:\n",
    "                        next_queue.append(node.left)\n",
    "                    if node.right:\n",
    "                        next_queue.append(node.right)\n",
    "                queue=next_queue\n",
    "            return i\n",
    "        if not root: return True\n",
    "        layer=[root]\n",
    "        while layer:\n",
    "            next_layer=[]\n",
    "            for node in layer:\n",
    "                if abs(depth(node.left)-depth(node.right))>1: return False\n",
    "                if node.left: next_layer.append(node.left)\n",
    "                if node.right: next_layer.append(node.right)\n",
    "            layer = next_layer\n",
    "        return True\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 迭代\n",
    "# class Solution:\n",
    "#     def isBalanced(self, root: TreeNode) -> bool:\n",
    "#         if not root: return True\n",
    "#         from collections import deque\n",
    "#         que = deque([root])\n",
    "#         left, right = 0, 0\n",
    "#         while que:\n",
    "#             size = len(que)\n",
    "#             for _ in range(size):\n",
    "#                 cur = que.popleft()\n",
    "#                 if cur.left:\n",
    "#                     que.append(cur.left)\n",
    "#                     left += 1\n",
    "#                 if cur.right:\n",
    "#                     que.append(cur.right)\n",
    "#                     right += 1\n",
    "#             print(left, right)\n",
    "#             if abs(left-right) > 1: return False \n",
    "#         return True\n",
    "\n",
    "# # 递归   \n",
    "# class Solution:\n",
    "#     def isBalanced(self, root: TreeNode) -> bool:     \n",
    "#         res = self.getHeight(root)\n",
    "#         return False if res == -1 else True\n",
    "\n",
    "#     def getHeight(self, node: TreeNode):\n",
    "#         if not node: return 0\n",
    "#         leftHeight = self.getHeight(node.left)\n",
    "#         if leftHeight == -1: return -1\n",
    "#         rightHeight = self.getHeight(node.right)\n",
    "#         if rightHeight == -1: return -1\n",
    "#         return max(leftHeight, rightHeight)+1 if abs(leftHeight-rightHeight) <= 1 else -1\n",
    "\n",
    "#迭代\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool: \n",
    "        que = []\n",
    "        if not root: return True\n",
    "        que.append(root)\n",
    "\n",
    "        while que:\n",
    "            cur = que.pop()\n",
    "            if abs(self.getDepth(cur.left) - self.getDepth(cur.right)) > 1:\n",
    "                return False\n",
    "            if cur.right:\n",
    "                que.append(cur.right)\n",
    "            if cur.left:\n",
    "                que.append(cur.left)\n",
    "        return True\n",
    "    \n",
    "    def getDepth(self, node):\n",
    "        que = []\n",
    "        if node:\n",
    "            que.append(node)\n",
    "        depth = 0\n",
    "        res = 0\n",
    "        while que:\n",
    "            cur = que.pop()\n",
    "            if cur:\n",
    "                que.append(cur)\n",
    "                que.append(None)\n",
    "                depth += 1\n",
    "                if cur.right: que.append(cur.right)\n",
    "                if cur.left: que.append(cur.left)\n",
    "            else:\n",
    "                cur = que.pop()\n",
    "                depth -= 1\n",
    "            res = max(res, depth)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        stack =[root]\n",
    "        height_map = {}\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "                if node.left: stack.append(node.left)\n",
    "                if node.right: stack.append(node.right)\n",
    "            else:\n",
    "                real_node = stack.pop()\n",
    "                left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0)\n",
    "                if abs(left - right) > 1:\n",
    "                    return False\n",
    "                height_map[real_node] = 1 + max(left, right)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "\n",
    "        height_map = {}\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "\n",
    "                if node.left: stack.append(node.left)\n",
    "                if node.right: stack.append(node.right)\n",
    "\n",
    "            else:\n",
    "                real_node = stack.pop()\n",
    "                left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0)\n",
    "                if abs(left - right) > 1:\n",
    "                    return False\n",
    "                height_map[real_node] = 1 + max(left, right)\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root==None:\n",
    "            return 0\n",
    "        height=0\n",
    "        q=Queue()\n",
    "        q.put(root)\n",
    "        q.put(None)\n",
    "        while(not q.empty()):\n",
    "            a=q.get()\n",
    "            if a==None:\n",
    "                height+=1\n",
    "                if q.qsize()!=0:\n",
    "                    q.put(None)\n",
    "            elif(a.left!=None or a.right!=None):\n",
    "                if a.left!=None:\n",
    "                    q.put(a.left)\n",
    "                if a.right!=None:\n",
    "                    q.put(a.right)\n",
    "        return height\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root==None:\n",
    "            return True\n",
    "        else:\n",
    "            left_height=self.maxDepth(root.left)\n",
    "            right_height=self.maxDepth(root.right)\n",
    "            if left_height==right_height:\n",
    "                return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "            else:\n",
    "                if left_height==right_height+1:\n",
    "                    return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "                elif left_height+1==right_height:\n",
    "                    return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        height_map = {} # 定义一个字典，用来存放每个节点的高度\n",
    "        stack = [root] # 将根节点放入栈中\n",
    "        while stack: # 当栈不为空的时候，循环遍历\n",
    "            node = stack.pop() # 将栈顶元素弹出\n",
    "            if node: # 如果栈顶元素不为空，就将其左右孩子和自身加入到栈中\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "                if node.left: stack.append(node.left) \n",
    "                if node.right: stack.append(node.right)\n",
    "            else: # 如果栈顶元素为空，说明遍历到了叶子节点，开始计算高度\n",
    "                real_node = stack.pop() # 将栈顶元素弹出\n",
    "                left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0) # 获取左右子树的高度\n",
    "                if abs(left - right) > 1: # 如果左右子树的高度差大于1，就返回False\n",
    "                    return False\n",
    "                height_map[real_node] = 1 + max(left, right) # 将当前节点的高度加入到字典中\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        que = collections.deque([root])\n",
    "\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                cur = que.popleft()\n",
    "                if abs(self.depth(cur.left) - self.depth(cur.right)) > 1:\n",
    "                    return False\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "        return True\n",
    "\n",
    "    def depth(self, node) -> int:\n",
    "        if not node:\n",
    "            return 0\n",
    "\n",
    "        queue = collections.deque([node])\n",
    "        depth = 0\n",
    "        while queue:\n",
    "            depth += 1\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return depth\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        height_map = {}\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "                if node.left: stack.append(node.left)\n",
    "                if node.right: stack.append(node.right)\n",
    "            else:\n",
    "                real_node = stack.pop()\n",
    "                left, right = height_map.get(real_node.left, 0), height_map.get(real_node.right, 0)\n",
    "                if abs(left - right) > 1:\n",
    "                    return False\n",
    "                height_map[real_node] = 1 + max(left, right)\n",
    "        return True\n",
    "        \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        que = [root]\n",
    "        while que:\n",
    "            cur = que.pop(0)\n",
    "            if abs(self.getdepth(cur.right) - self.getdepth(cur.left)) > 1:\n",
    "                return False\n",
    "\n",
    "            if cur.left:\n",
    "                que.append(cur.left)\n",
    "            if cur.right:\n",
    "                que.append(cur.right)        \n",
    "        return True\n",
    "    def getdepth(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        que = [node]\n",
    "        count = 0\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                cur = que.pop(0)\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "            count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        def js(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            dui = collections.deque([root])\n",
    "            jg = []\n",
    "            while(dui):\n",
    "                level = []\n",
    "                for i in range(len(dui)):\n",
    "                    top = dui.popleft()\n",
    "                    level.append(top.val)\n",
    "                    if(top.left):\n",
    "                        dui.append(top.left)\n",
    "                    if(top.right):\n",
    "                        dui.append(top.right)\n",
    "                jg.append(level)\n",
    "            return len(jg)\n",
    "        \n",
    "        st = []\n",
    "        if not root:\n",
    "            return True\n",
    "        st.append(root)\n",
    "        while(st):\n",
    "            top = st.pop()\n",
    "            if top:\n",
    "                if top.right:\n",
    "                    st.append(top.right)\n",
    "                \n",
    "\n",
    "                if top.left:\n",
    "                    st.append(top.left)\n",
    "\n",
    "                st.append(top)\n",
    "                st.append(None)\n",
    "            else:\n",
    "                top = st.pop()\n",
    "                if(js(top.left)-js(top.right)>1 or js(top.right)-js(top.left)>1):\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        status,_=self.find(root)\n",
    "        return status\n",
    "        \n",
    "\n",
    "    def find(self,root):\n",
    "        if root is None:\n",
    "            print('none')\n",
    "            return True,0\n",
    "\n",
    "        print(root.val)\n",
    "\n",
    "        lef_status,depth_left=self.find(root.left)\n",
    "        right_status,depth_right=self.find(root.right)\n",
    "\n",
    "        print('oooo',root.val,lef_status,right_status)\n",
    "        if (not lef_status) or ( not right_status):\n",
    "            return False,0\n",
    "\n",
    "        if abs(depth_left-depth_right)>1:\n",
    "            status=False\n",
    "        else:\n",
    "            status=True\n",
    "\n",
    "        print('----------',status)\n",
    "        return status,1+max(depth_right,depth_left)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def isBalanced(self, root):\n",
    "        def Balance(root):\n",
    "            if (not root):\n",
    "                return True\n",
    "            return check(root) and Balance(root.left) and Balance(root.right)\n",
    "            \n",
    "        def find_depth(root):\n",
    "            if(not root): \n",
    "                return 0\n",
    "            \n",
    "            d1 = find_depth(root.left)\n",
    "            d2 = find_depth(root.right)\n",
    "            return max(d1,d2)+1\n",
    "        \n",
    "        \n",
    "        def check(root):\n",
    "            if(not root):\n",
    "                return True\n",
    "            dd1 = find_depth(root.left)\n",
    "            dd2 = find_depth(root.right)\n",
    "            if abs(dd1-dd2)<=1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        return Balance(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        # 当前节点需要干什么\n",
    "        if not root: return True\n",
    "        if abs(self.depth(root.left) - self.depth(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "    \n",
    "    # 计算树的（最大）深度\n",
    "    def depth(self, root):\n",
    "        return 0 if not root else 1 + max(self.depth(root.left), self.depth(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        self.isValid = True\n",
    "        self.maxDepth(root)\n",
    "        return self.isValid\n",
    "\n",
    "\n",
    "    def maxDepth(self, root):\n",
    "        if not root: return 0\n",
    "        if not self.isValid: return -999\n",
    "        leftMaxDepth = self.maxDepth(root.left)\n",
    "        rightMaxDepth = self.maxDepth(root.right)\n",
    "        if abs(leftMaxDepth - rightMaxDepth) > 1:\n",
    "            self.isValid = False\n",
    "        return max(leftMaxDepth, rightMaxDepth) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if self.get_height(root) != -1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def get_height(self, root: TreeNode) -> int:\n",
    "        # Base Case\n",
    "        if not root:\n",
    "            return 0\n",
    "        # 左\n",
    "        if (left_height := self.get_height(root.left)) == -1:\n",
    "            return -1\n",
    "        # 右\n",
    "        if (right_height := self.get_height(root.right)) == -1:\n",
    "            return -1\n",
    "        # 中\n",
    "        if abs(left_height - right_height) > 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return 1 + max(left_height, right_height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        \n",
    "        flag1 = self.isBalanced(root.left)\n",
    "        flag2 = self.isBalanced(root.right)\n",
    "        flag3 = abs(self.height(root.left) - self.height(root.right)) <=1\n",
    "        return flag1 and flag2 and flag3\n",
    "\n",
    "    \n",
    "    def height(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.height(root.left), self.height(root.right)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def depth(root):\n",
    "    if not root:\n",
    "        return 0\n",
    "    return max(depth(root.left), depth(root.right))+1\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        # print(depth(root))\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(depth(root.left) - depth(root.right)) <=1 and self.isBalanced(root.left) and self.isBalanced(root.right):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \\\n",
    "            self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def depth(self, root):\n",
    "        # if not root.left and not root.right : return 0\n",
    "        if not root: return 0\n",
    "        return max(self.depth(root.left), self.depth(root.right))+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        def fun(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            left_length=fun(node.left)\n",
    "            right_length=fun(node.right)\n",
    "            if left_length==-1 or right_length == -1:\n",
    "                return -1\n",
    "            if abs(left_length-right_length)>1:\n",
    "                return -1\n",
    "            return max(left_length,right_length)+1\n",
    "        return fun(root)!=-1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root:TreeNode):\n",
    "        if root == None:\n",
    "            return True\n",
    "        left = self.height(root.left)\n",
    "        right = self.height(root.right)\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and \\\n",
    "               abs(self.height(root.left)-self.height(root.right))<=1\n",
    "\n",
    "\n",
    "\n",
    "    def height(self, root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        lefth = self.height(root.left)\n",
    "        righth = self.height(root.right)\n",
    "        if lefth == -1 or righth == -1 or abs(lefth-righth)>1:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(lefth,righth) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "    def depth(self,root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.depth(root.left),self.depth(root.right)) + 1\n",
    "\n",
    "        # def recur(root):\n",
    "        #     if not root:\n",
    "        #         return 0\n",
    "        #     left = recur(root.left)\n",
    "        #     if left == -1:\n",
    "        #         return -1\n",
    "        #     right = recur(root.right)\n",
    "        #     if right == -1:\n",
    "        #         return -1\n",
    "        #     return max(left,right) + 1 if abs(left-right) <= 1 else -1\n",
    "        # return recur(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        def traversal(node):\n",
    "            if node == None:\n",
    "                return 0, True\n",
    "            left, left_flag = traversal(node.left)\n",
    "            right, rigt_flag = traversal(node.right)\n",
    "            if left_flag == False or rigt_flag == False:\n",
    "                return 0, False\n",
    "            if abs(left - right) > 1:\n",
    "                return 0, False\n",
    "            return max(right,left) + 1, True\n",
    "        \n",
    "        _, f = traversal(root)\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        return self.getHeight(root) != -1\n",
    "\n",
    "    def getHeight(self, node):\n",
    "        if not node:\n",
    "            return 0 \n",
    "        leftHeight = self.getHeight(node.left)\n",
    "        rightHeight = self.getHeight(node.right)\n",
    "        if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:\n",
    "            return -1          \n",
    "        return max(leftHeight, rightHeight) + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
